#include<stdio.h>
#include<stdlib.h>
#define N 10
#define M 10
int Available[N];
int Claim[N][M];
int Allocation[N][M];
int Need[N][M];
int Request[M];
int Work[N];
bool possible[N];
int Safequeue[N];
int Resources[M];
int process_num;
int resources_num;

void input()
{
    printf("输入进程个数：");
    scanf("%d",&process_num);
    printf("输入资源种类数：");
    scanf("%d",&resources_num);
    printf("输入各类资源总数：");
    for(int i=0;i<resources_num;i++)
    {
        scanf("%d",&Resources[i]);
        Available[i]=Resources[i];
    }
    printf("输入进程对资源最大需求量Claim(A B C)：\n");
    for(int i=0;i<process_num;i++)
    {
        printf("进程%d：",i);
        for(int j=0;j<resources_num;j++)
        {
            scanf("%d",&Claim[i][j]);
        }
    }
    printf("输入已分配资源Allocation(A B C)：\n");
    for(int i=0;i<process_num;i++)
    {
        printf("进程%d：",i);
        for(int j=0;j<resources_num;j++)
        {
            scanf("%d",&Allocation[i][j]);
            Available[j]-=Allocation[i][j];
            Need[i][j]=Claim[i][j]-Allocation[i][j];
        }
    }
}

void print1()
{
    printf("系统目前情况如下：");
    printf("\n      Claim\t  Allocation\t  Need\n");
    for(int i=0;i<process_num;i++)
    {
        printf("P%d  ",i);
        for(int j=0;j<resources_num;j++)
            printf("%-2d  ",Claim[i][j]);
        printf("  ");
        for(int j=0;j<resources_num;j++)
            printf("%-2d  ",Allocation[i][j]);
        printf("  ");
        for(int j=0;j<resources_num;j++)
            printf("%-2d  ",Need[i][j]);
        putchar('\n');
    }
    printf("Availble：");
    for(int i=0;i<resources_num;i++)
        printf("%d ",Available[i]);
    putchar('\n');
}

void print()
{
    for(int i=0;i<resources_num;i++)
        Work[i]=Available[i];
    printf("    Work\t Need\t   Allocation  Work+Allocation possible\n");
    for(int i=0;i<process_num;i++)
    {
        printf("P%d  ",Safequeue[i]);
        for(int j=0;j<resources_num;j++)
            printf("%-2d ",Work[j]);
        printf("  ");
        for(int j=0;j<resources_num;j++)
            printf("%-2d ",Need[Safequeue[i]][j]);
        printf("  ");
        for(int j=0;j<resources_num;j++)
            printf("%-2d ",Allocation[Safequeue[i]][j]);
        printf("  ");
        for(int j=0;j<resources_num;j++)
            printf("%-2d ",Allocation[Safequeue[i]][j]+Work[j]);
        if(possible[i]==1)
            printf("\t  true");
        else
            printf("\t  false");
        printf("\n");
        for(int j=0;j<resources_num;j++)
            Work[j]+=Allocation[Safequeue[i]][j];
    }

    printf("存在安全序列：");
    for(int i=0;i<process_num;i++)
    {
        printf("P%d",Safequeue[i]);
        if(i!=process_num-1)
            printf("->");
    }
    putchar('\n');
}

int isSafe()
{
    int flag=1;
    int bFlag=0;
    int rest[N];
    int k=0;
    printf("\n安全性检查：\n");
    for(int i=0;i<resources_num;i++)
        Work[i]=Available[i];
    for(int i=0;i<process_num;i++)
        rest[i]=i;
    while(1)
    {
        bFlag=0;
        for(int i=0;i<process_num;i++)
        {
            if(rest[i]!=-1)
                break;
        }
        int i;
        if(i==process_num)
            break;
        for(int i=0;i<process_num;i++)
        {
            if(rest[i]==-1)
                continue;
            for(int j=0;j<resources_num;j++)
            {
                if(Need[i][j]>Work[j])
                {
                    flag=0;
                    bFlag++;
                    possible[i]=false;
                    break;
                }
            }
            if(flag)
            {
                for(int j=0;j<resources_num;j++)
                    Work[j]+=Allocation[i][j];
                Safequeue[k++]=i;
                rest[i]=-1;
                possible[i]=true;
            }
            flag=1;
        }
        if(bFlag==process_num)
            break;
        /* code */
    }
    for(int i=0;i<process_num;i++)
    {
        if(rest[i]!=-1)
        {
            printf("系统不安全...");
            return 0;
        }
    }
    print();
    printf("系统安全...\n");
    return 1;
}
void bank()
{
    printf("        银行家算法      \n");
    input();
    print1();
    if(!isSafe())
        exit(0);
    int p;
    while(1)
    {
        int flag=1;
        printf("\n输入申请资源的进程号：");
        scanf("%d",&p);
        printf("输入进程请求资源数量Request(a,b,c)：");
        for(int i=0;i<resources_num;i++)
            scanf("%d",&Request[i]);
        for(int i=0;i<resources_num;i++)
            if(Request[i]>Need[p][i])        
            {
                flag=0;
                printf("进程申请量超过所需求量,让该进程等待\n");
                printf("\n请重新输入：\n");
                break;
            }
        if(flag)
            printf("进程申请量不超其需求量!\n");
        else    
            continue;
            /* code */
        flag=1;
        for(int i=0;i<resources_num;i++)
            if(Request[i]>Available[i])
            {
                flag=0;
                printf("进程申请量超过当前系统所拥有资源量,让该进程等待!\n");
                printf("\n请重新输入：\n");
                break;
            }
        if(flag)
            printf("进程申请量不超当前系统所拥有的资源量!\n");
        else
            continue;
        printf("试探性分配资源：\n");
        for(int i=0;i<resources_num;i++)
        {
            Available[i]-=Request[i];
            Allocation[p][i]+=Request[i];
            Need[p][i]-=Request[i];
        }
        print1();
        if(!isSafe())
        {
            for(int i=0;i<resources_num;i++)
            {
                Available[i]+=Request[i];
                Allocation[p][i]-=Request[i];
                Need[p][i]+=Request[i];
            }
            printf("\n试探性分配作废,系统恢复原来状态!\n");
            print1();
        }
        else    printf("资源分配成功!\n");
        
        

        
    }
}
int main()
{
    bank();
    return 0;
}